package top.minuy.structure.graph.mst;

import top.minuy.structure.graph.cc.bfs.WeightedCC;
import top.minuy.structure.graph.representations.WeightedEdge;
import top.minuy.structure.graph.representations.table.WeightedGraph;

import java.util.ArrayList;
import java.util.List;

/**
 * Prim算法，第一版
 *
 * @author Minuy
 * @time 17:18
 * @date 2021/11/25
 */
public class Prim {

    List<WeightedEdge> mst;

    public Prim(WeightedGraph g){

        mst = new ArrayList<>();

        WeightedCC cc = new WeightedCC(g);
        if (cc.count()!=1){
            return;
        }

        // Prim算法：
        boolean[] isVisited = new boolean[g.V()];
        isVisited[0] = true; // 蓝色
        for (int e=1;e<g.V();e++){ // 寻找v-1次最短横切边
            WeightedEdge minEdge = new WeightedEdge(-1,-1,Integer.MAX_VALUE);
            for (int v=0;v<g.V();v++){ // 遍历所有的顶点
                if (isVisited[v]){ // 顶点是蓝色的
                    for (int w:g.adj(v)){ // 看看是不是有绿色的顶点相邻
                        if (!isVisited[w]){ // 绿色
                            // w-v肯定是横切边
                            WeightedEdge edge = new WeightedEdge(w,v,g.getWeight(w,v));
                            minEdge = edge.compareTo(minEdge)<0?edge:minEdge;
                        }
                    }
                }
            }
            // 在这就找到了最小的横切边
            mst.add(minEdge);
            isVisited[minEdge.w] = true; // 都变成蓝色的
            isVisited[minEdge.v] = true;
        }
    }


    /**
     * 获取最小生成树
     * @return Iterable<WeightedEdge> 最小生成树的所有边
     * @author Minuy
     * @date 2021/11/25 16:47
     */
    public Iterable<WeightedEdge> mst(){
        return mst;
    }

    @Override
    public String toString() {
        return mst().toString();
    }
}
